package com.mrl.linkedlist;


import java.util.Stack;

/**
 * 单向链表
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        // 创建一个单向链表
        SingleLinedList singleLinedList = new SingleLinedList();
        // 向单向链表添加数据
        singleLinedList.addByOrder(new HeroNode(1, "宋江", "及时雨"));
        singleLinedList.addByOrder(new HeroNode(3, "吴用", "智多星"));
        singleLinedList.addByOrder(new HeroNode(4, "林冲", "豹子头"));
        singleLinedList.addByOrder(new HeroNode(2, "卢俊宇", "玉麒麟"));
        // 展示链表
        System.out.println("修改前~~");
        singleLinedList.list();

        // 修改链表
        singleLinedList.update(new HeroNode(2, "林哥哥", "豹子头～～～～～"));
        // 重新展示链表
        System.out.println("修改后~~");
        singleLinedList.list();

        // 删除节点
        singleLinedList.delete(3);
        // 重新展示链表
        System.out.println("删除后~~");
        singleLinedList.list();

        // 链表的节点个数
        System.out.println("链表的节点个数为 ==> " + getLength(singleLinedList.getHead()));

        // 获取第 -2 个节点
        System.out.println("第-2个节点为："  + getLastIndexNode(singleLinedList.getHead(), 2));

        // 测试翻转
        reverseLinkedList(singleLinedList.getHead());
        System.out.println("翻转~~");
        singleLinedList.list();

        // 逆向输出
        reversePrint(singleLinedList.getHead());
    }

    /**
     * 逆向输出（使用栈）
     * @param head 链表的头指针
     */
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            System.out.println("链表为空~~");
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode tmp = head.next;
        while (tmp != null) {
            stack.add(tmp);
            tmp = tmp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 翻转链表（腾讯面试题）
     * @param head 链表的头结点
     */
    public static void reverseLinkedList(HeroNode head) {
        // 元素个数为1个或0个时无需进行操作
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode reverseHead = new HeroNode(0, "", "");
        HeroNode tmp = head.next;
        HeroNode tmpNext = tmp.next;
        while (tmp != null) {
            tmpNext = tmp.next;
            tmp.next = reverseHead.next;
            reverseHead.next = tmp;
            tmp = tmpNext;
        }
        head.next = reverseHead.next;
    }

    /**
     * 获取链表中第 -index 个节点
     * @param head 链表头
     * @param index 查找的位置
     * @return 如果存在则返回节点，不存在返回null
     */
    public static HeroNode getLastIndexNode(HeroNode head, int index) {
        if (head.next == null || index <= 0) {
            return null;
        }
        // 获取链表长度
        int length = getLength(head);
        if (index > length) {
            return null;
        }
        HeroNode tmp = head.next;
        for (int i = 0;i < length - index;i ++) {
            tmp = tmp.next;
        }
        return tmp;
    }

    /**
     * 获取节点个数
     * @param head 链表的头节点
     * @return 返回节点个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        int length = 0;
        HeroNode tmp = head.next;
        while (tmp != null) {
            length ++;
            tmp = tmp.next;
        }
        return length;
    }
}

/**
 * 链表对象
 */
class SingleLinedList {
    private HeroNode head;

    SingleLinedList() {
        head = new HeroNode(0, "", "");
    }

    /**
     * 获取头节点
     * @return 返回一个头结点
     */
    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加元素到链表
     */
    public void add(HeroNode heroNode) {
        HeroNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = heroNode;
    }

    /**
     * 排序插入元素到链表
     */
    public void addByOrder(HeroNode heroNode) {
        HeroNode tmp = head;
        boolean flag = false;
        while (tmp.next != null) {
            if (tmp.next.no > heroNode.no) {
                break;
            }else if (tmp.next.no == heroNode.no) {
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if (flag) {
            System.out.println("已存在相同的编号, 插入失败");
        }else {
            heroNode.next = tmp.next;
            tmp.next = heroNode;
        }
    }

    /**
     * 修改链表数据
     */
    public void update(HeroNode newHeroNode) {
        HeroNode tmp = head;
        boolean find = false;
        while (tmp.next != null) {
            if (tmp.no == newHeroNode.no) {
                find = true;
                break;
            }
            tmp = tmp.next;
        }
        if (find) {
            tmp.name = newHeroNode.name;
            tmp.nickname = newHeroNode.nickname;
        }else {
            System.out.printf("没有找到编号为 %d 的对象\n", newHeroNode.no);
        }
    }

    /**
     * 删除节点
     */
    public void delete(int no) {
        HeroNode tmp = head;
        boolean find = false;
        while (tmp.next != null) {
            if (tmp.next.no == no) {
                find = true;
                break;
            }
            tmp = tmp.next;
        }
        if (find) {
            tmp.next = tmp.next.next;
        }else {
            System.out.printf("未找到编号为 %d 的节点", no);
        }
    }

    /**
     * 展示链表数据
     */
    public void list() {
        HeroNode tmp = head;
        while (tmp.next != null) {
            System.out.println(tmp.next);
            tmp = tmp.next;
        }
    }
}

/**
 * 链表节点
 */
class HeroNode {
    // 编号
    public int no;
    // 姓名
    public String name;
    // 昵称
    public String nickname;
    // next指针
    public HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}


